package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;


public class DFS_6 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }

    // 构建深度优先生成树的方法，接受起始节点作为参数
    public static ArrayList<Edge> generateTree(Node start) {
        // 创建一个列表来存储生成树的边
        ArrayList<Edge> treeEdges = new ArrayList<>();
        // 创建一个栈来辅助深度优先搜索
        Stack<Node> stack = new Stack<>();
        boolean[] visited = new boolean[100]; // 假设图中最多有100个节点，根据实际情况调整大小
        stack.push(start);
        visited[start.value] = true;
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            for (Node neighbor : current.neighbors) {
                if (!visited[neighbor.value]) {
                    // 将边添加到生成树边列表中
                    treeEdges.add(new Edge(current.value, neighbor.value));
                    stack.push(neighbor);
                    visited[neighbor.value] = true;
                }
            }
        }
        return treeEdges;
    }

    // 定义边类
    static class Edge {
        int from;
        int to;

        Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }
}